package lc2

/*
 * @lc app=leetcode.cn id=2 lang=golang
 *
 * [2] 两数相加
给你两个 非空 的链表，表示两个非负的整数。
它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
*/

// ListNode ...
type ListNode struct {
	Val  int
	Next *ListNode
}

// @lc code=start

// addTwoNumbers 逆序，[1,2,3,4]+[1,2,3]=[2,4,6,4]
// 思路：将 l2 叠加到 l1 上，叠加时处理进位，最后需要再处理一次进位
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := l1
	carry := 0 // 进位
	for {
		if l2 == nil && carry == 0 { // 提前结束
			break
		}
		// 将l2加到l1上，包括上一次的进位 l1.Val=l1.Val+l2.Val+addVal
		val := l1.Val + carry
		if l2 != nil {
			val += l2.Val
		}
		l1.Val = val % 10
		carry = val / 10
		// 如果 l1 结束了，把 l2 移到 l1 上，保证 len(l1)>len(l2)
		if l1.Next == nil && l2 != nil && l2.Next != nil {
			l1.Next = l2.Next
			l2.Next = nil
		}
		if l1.Next == nil { // 遍历完成退出, 处理最后的进位情况
			if carry > 0 {
				l1.Next = &ListNode{Val: carry}
			}
			break
		}
		// 继续遍历(此时可能只剩下l1,也可能l1,l2都有)
		l1 = l1.Next
		if l2 != nil {
			l2 = l2.Next
		}
	}
	return head
}

// @lc code=end
